package com.sheng.leetcode.year2023.month05.day23;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author liusheng
 * @date 2023/05/23
 * <p>
 * 1090. 受标签影响的最大值<p>
 * <p>
 * 我们有一个 n 项的集合。给出两个整数数组 values 和 labels ，<p>
 * 第 i 个元素的值和标签分别是 values[i] 和 labels[i]。还会给出两个整数 numWanted 和 useLimit 。<p>
 * 从 n 个元素中选择一个子集 s :<p>
 * 子集 s 的大小 小于或等于 numWanted 。<p>
 * s 中 最多 有相同标签的 useLimit 项。<p>
 * 一个子集的 分数 是该子集的值之和。<p>
 * 返回子集 s 的最大 分数 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1<p>
 * 输出：9<p>
 * 解释：选出的子集是第一项，第三项和第五项。<p>
 * <p>
 * 示例 2：<p>
 * 输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2<p>
 * 输出：12<p>
 * 解释：选出的子集是第一项，第二项和第三项。<p>
 * <p>
 * 示例 3：<p>
 * 输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1<p>
 * 输出：16<p>
 * 解释：选出的子集是第一项和第四项。<p>
 * <p>
 * 提示：<p>
 * n == values.length == labels.length<p>
 * 1 <= n <= 2 * 10^4<p>
 * 0 <= values[i], labels[i] <= 2 * 10^4<p>
 * 1 <= numWanted, useLimit <= n<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/largest-values-from-labels">1090. 受标签影响的最大值</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1090 {

    @Test
    public void test01() {
//        int[] values = {5, 4, 3, 2, 1}, labels = {1, 1, 2, 2, 3};
//        int numWanted = 3, useLimit = 1;
//        int[] values = {5, 4, 3, 2, 1}, labels = {1, 3, 3, 3, 2};
//        int numWanted = 3, useLimit = 2;
        int[] values = {9, 8, 8, 7, 6}, labels = {0, 0, 0, 1, 1};
        int numWanted = 3, useLimit = 1;
        System.out.println(new Solution().largestValsFromLabels(values, labels, numWanted, useLimit));
    }
}

class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        // 题目解读：要求从数组中选出一个子集，子集的数量 <= numWanted，子集中相同标签最多只能有 useLimit 个，求子集值的和最大为多少
        int length = values.length;
        int[][] nums = new int[length][2];
        for (int i = 0; i < length; i++) {
            nums[i][0] = values[i];
            nums[i][1] = labels[i];
        }
        Arrays.sort(nums, (o1, o2) -> o2[0] - o1[0]);
        Map<Integer, Integer> map = new HashMap<>();
        int index = 0;
        int ans = 0;
        for (int i = 0; i < numWanted && index < length; i++) {
            while (index < length && map.containsKey(nums[index][1]) && map.get(nums[index][1]) == useLimit) {
                index++;
            }
            if (index == length) {
                break;
            }
            ans += nums[index][0];
            map.put(nums[index][1], map.getOrDefault(nums[index][1], 0) + 1);
            index++;
        }
        return ans;
    }
}
